package practice;

public class LeetCode3 {
	public static void main(String[] args) {
		int t = new Solution3An().lengthOfLongestSubstring("abasasfdsa");
		System.out.println(t);
	}
}

class Solution3 {
	public int lengthOfLongestSubstring(String s) {
		if("".equals(s)) return 0;
		int len = s.length();
		// 补位,不然最后一位会出问题
		s = s + s.charAt(s.length()-1);
		char[] arr = s.toCharArray();
		int i = 0, j = 1, t = 1, k, temp = 1;
		while(i < j && j <= len) {
			// 判断 j 下标与 i-j 中的字母是否有相同的，如果有相同的就将 temp = 0
			for(k=i; k<j; k++) {
				// 如果有相同的
				if(arr[k] == arr[j]) {
					//System.out.println("i="+i+";"+"j="+j);
					if(j - i > t) t = j - i;
					if(k > i) {
						i = k;
					} else {
						i++;
					}
					j = i + 1;
					temp = 0;
					break;
				}
				temp = 1;
			}
			if(temp == 1) j ++;
		}
		return t;
	}
}

class Solution3An {
	/* 击败 100% 的代码		eg:abasasfdsa*/
	public int lengthOfLongestSubstring(String s) {
		int[] last = new int[128];
		int n = s.length();
		int res = 0;
		int start = 0; // 窗口开始位置

		for(int i = 0; i < n; i++) {
			int index = s.charAt(i);
			start = Math.max(start, last[index]);
			res = Math.max(res, i - start + 1);
			last[index] = i+1;
		}
		return res;
	}
}

